/*
 * Copyright 2011 The Emscripten Authors.  All rights reserved.
 * Emscripten is available under two separate licenses, the MIT license and the
 * University of Illinois/NCSA Open Source License.  Both these licenses can be
 * found in the LICENSE file.
 */

#include <stdio.h>
#include <malloc.h>
#include <emscripten/emscripten.h>



int InsertSort(long long array[], int left, int right);
int GetPivotIndex(long long array[], int left, int right);
int Partition(long long array[], int left, int right, int pivot_index);
int BFPRT(long long array[], int left, int right, int k);
void swap(long long* p1, long long* p2);


int main()
{
	printf("hello, world!\n");
	return 0;
}







#ifdef __cplusplus
extern "C" {
#endif

	int* playRecipes;
	int* playChefs;
	int* recipe2Change;
	int* scoreCacheNoEquipIndex;
	int* scoreAddCacheNoEquip;
	short* disordePermuation;

	int recipe2ChangeLength;
	int scoreAddCacheNoEquipLength;
	int scoreCacheNoEquipIndexLength;

	int tomNum = 200000;


    int  EMSCRIPTEN_KEEPALIVE checkDataValid(){
        return disordePermuation[0]+disordePermuation[1]+disordePermuation[2]+disordePermuation[3];
    }


	/**
	* playRecipes               二维数组
	* playChefs                 二维数组
	* recipe2Change     一维数组
	* scoreCacheNoEquipIndex    二维数组
	* scoreAddCacheNoEquip      二维数组
	*/

	int  EMSCRIPTEN_KEEPALIVE init(int* playRecipes1, int* playChefs1, int* recipe2Change1, int* scoreCacheNoEquipIndex1, int* scoreAddCacheNoEquip1, short* disordePermuation1) {
		playRecipes = playRecipes1;
		playChefs = playChefs1;

		recipe2ChangeLength = recipe2Change1[0];
		scoreAddCacheNoEquipLength = scoreAddCacheNoEquip1[1];
		scoreCacheNoEquipIndexLength = scoreCacheNoEquipIndex1[1];


		recipe2Change = (int*)(recipe2Change1 + 1);
		scoreCacheNoEquipIndex = (int*)(scoreCacheNoEquipIndex1 + 2);
		scoreAddCacheNoEquip = (int*)(scoreAddCacheNoEquip1 + 2);
		disordePermuation = (short*)(disordePermuation1 + 2);

		return recipe2ChangeLength;
	}


	long long* EMSCRIPTEN_KEEPALIVE call(int start, int limit, long long topKScore) {

		long long topKValue = topKScore;
		register  int topKValueInt = (int)((topKValue & 0xfffff00000000000L) >> 43);

		int index = 0;
		long long* scores = (long long*)malloc(sizeof(long long) * (1680 * playChefs[0] + tomNum));

		int score1Index = 0, score2Index = 0, score3Index = 0;

		int* playChefOffset4 = (int*)(playChefs + 4);
		int* playChefOffset7 = (int*)(playChefs + 7);
		int* playChefOffset10 = (int*)(playChefs + 10);
		for (int i = start; i < limit; i++) {
			int* precipes = (int*)(playRecipes + 2 + i * playRecipes[1]);

			long long cal = 0, cal2 = 0, cal3 = 0;
			for (int k = 0; k < 1680; k++) {
				short* ints = &(disordePermuation[k * 9]);

				score1Index = *(scoreCacheNoEquipIndex + precipes[ints[0]] * scoreCacheNoEquipIndexLength + precipes[ints[1]]) + (precipes[ints[2]] - precipes[ints[1]] - 1);
				score2Index = *(scoreCacheNoEquipIndex + precipes[ints[3]] * scoreCacheNoEquipIndexLength + precipes[ints[4]]) + (precipes[ints[5]] - precipes[ints[4]] - 1);
				score3Index = *(scoreCacheNoEquipIndex + precipes[ints[6]] * scoreCacheNoEquipIndexLength + precipes[ints[7]]) + (precipes[ints[8]] - precipes[ints[7]] - 1);

				int* scoreAddCacheNoEquip2 = (int*)(scoreAddCacheNoEquip + score3Index);

				int score1 = 0, score2 = 0;
				int i9 = 0;

				for (int chef2LimitIndex = 0; chef2LimitIndex < recipe2ChangeLength; chef2LimitIndex++) {
					int* playChef = (int*)(playChefs + i9 * 3 + 2);


					score2 = *(scoreAddCacheNoEquip + playChef[0] * scoreAddCacheNoEquipLength + score1Index) + *(scoreAddCacheNoEquip + playChef[1] * scoreAddCacheNoEquipLength + score2Index);


					int  chef2Limit = recipe2Change[chef2LimitIndex] - 1;

					for (int i99 = i9 * 3; i9 < chef2Limit; i9 += 2, i99 += 6) {

						cal = score2 + *(scoreAddCacheNoEquip2 + (*(playChefOffset4 + i99)) * scoreAddCacheNoEquipLength);

						cal2 = score2 + *(scoreAddCacheNoEquip2 + (*(playChefOffset7 + i99)) * scoreAddCacheNoEquipLength);


						if (cal > topKValue) {
							// i k ,i9   菜谱 i(0-2304)12位，  菜谱排列 k(0-1680)11位，  厨师组合 i2(0-795)12位
							//将得分， 菜谱，菜谱排列，厨师组合索引组合成long保存， 得分(cal)在高位，这样新的cal可以用来排序
							// 1符号位，20位得分，18位菜谱索引，11位菜谱排列，14位厨师索引
							cal = ((((cal << 18 | i) << 11) | k) << 14) | i9;
							scores[index++] = cal;
						}

						if (cal2 > topKValue) {
							cal2 = ((((cal2 << 18 | i) << 11) | k) << 14) | (i9 + 1);
							scores[index++] = cal2;
						}

					}

					if (chef2Limit == i9) {
						cal = score2 + *(scoreAddCacheNoEquip2 + (*(playChefOffset4 + i9 * 3)) * scoreAddCacheNoEquipLength);

						if (cal > topKValue) {
							cal = ((((cal << 18 | i) << 11) | k) << 14) | i9;
							scores[index++] = cal;
						}
						i9++;
					}

				}
			}

			if ((index - tomNum) > 0) {
				//排序，只保留tomNum个结果
				topKValue = scores[BFPRT(scores, 0, index, index - tomNum)];
				topKValueInt = (int)((topKValue & 0xfffff00000000000L) >> 43);
				int newIndex = 0;
				for (int j = 0; j < index; j++) {
					if (scores[j] > topKValue) {
						scores[newIndex++] = scores[j];
					}
				}
				index = newIndex;
			}
		}

		long long* resultScores = (long long*)malloc(sizeof(long long) * ((index - tomNum) > 0 ? tomNum : index));



		topKValue = 0;

		if ((index - tomNum) > 0) {
			topKValue = scores[BFPRT(scores, 0, index, index - tomNum)];
		}

		int  k = 1;
		for (int i = 0; i < index; i++) {
			if (scores[i] > topKValue) {
				resultScores[k++] = scores[i];
			}
		}
		resultScores[0] = k;

		return resultScores;
	}



#ifdef __cplusplus
}
#endif



void swap(long long* p1, long long* p2) {
	long long tmp = *p1;   //p1指向的变量的值，赋值给tempt
	*p1 = *p2;       //p2指向的变量的值，赋值给p1指向的变量
	*p2 = tmp;       //temp的值，赋值给p2指向的变量
}


/**
 * 对数组 array[left, right] 进行插入排序，并返回 [left, right]
 * 的中位数。
 */
int InsertSort(long long array[], int left, int right)
{
	long long temp;
	int j;

	for (int i = left + 1; i <= right; i++)
	{
		temp = array[i];
		j = i - 1;

		while (j >= left && array[j] > temp)
		{
			array[j + 1] = array[j];
			j--;
		}

		array[j + 1] = temp;
	}

	return ((right - left) >> 1) + left;
}

/**
 * 数组 array[left, right] 每五个元素作为一组，并计算每组的中位数，
 * 最后返回这些中位数的中位数下标（即主元下标）。
 *
 * @attention 末尾返回语句最后一个参数多加一个 1 的作用其实就是向上取整的意思，
 * 这样可以始终保持 k 大于 0。
 */
int GetPivotIndex(long long array[], int left, int right)
{
	if (right - left < 5)
		return InsertSort(array, left, right);

	int sub_right = left - 1;

	// 每五个作为一组，求出中位数，并把这些中位数全部依次移动到数组左边
	for (int i = left; i + 4 <= right; i += 5)
	{
		int index = InsertSort(array, i, i + 4);
		swap(&array[++sub_right], &array[index]);
	}

	// 利用 BFPRT 得到这些中位数的中位数下标（即主元下标）
	return BFPRT(array, left, sub_right, ((sub_right - left + 1) >> 1) + 1);
}

/**
 * 利用主元下标 pivot_index 进行对数组 array[left, right] 划分，并返回
 * 划分后的分界线下标。
 */
int Partition(long long array[], int left, int right, int pivot_index)
{
	swap(&array[pivot_index], &array[right]); // 把主元放置于末尾

	int partition_index = left; // 跟踪划分的分界线
	for (int i = left; i < right; i++)
	{
		if (array[i] < array[right])
		{
			swap(&array[partition_index++], &array[i]); // 比主元小的都放在左侧
		}
	}

	swap(&array[partition_index], &array[right]); // 最后把主元换回来

	return partition_index;
}
/**
 * 返回数组 array[left, right] 的第 k 小数的下标
 */
int BFPRT(long long array[], int left, int right, int k)
{
	int pivot_index = GetPivotIndex(array, left, right); // 得到中位数的中位数下标（即主元下标）
	int partition_index = Partition(array, left, right, pivot_index); // 进行划分，返回划分边界
	int num = partition_index - left + 1;

	if (num == k)
		return partition_index;
	else if (num > k)
		return BFPRT(array, left, partition_index - 1, k);
	else
		return BFPRT(array, partition_index + 1, right, k - num);
}
